W razie problemów technicznych ze Szkopułem, prosimy o kontakt mailowy pod adresem [email protected].
Jeśli chciałbyś porozmawiać o zadaniach, rozwiązaniach lub problemach technicznych, zapraszamy na serwery Discord. Są one moderowane przez społeczność, ale członkowie zespołu technicznego też są tam aktywni.
Mamy naszyjnik złożony z koralików, z których każdy jest jednego z rodzajów. Koraliki numerujemy liczbami całkowitymi od do . Koralik o numerze sąsiaduje w naszyjniku z koralikami o numerach oraz (o ile koraliki o takich numerach istnieją), a ponadto koraliki o numerach oraz również sąsiadują ze sobą. Chcemy podzielić naszyjnik dwoma cięciami na dwie niepuste części tak, aby każdy rodzaj koralika występował dokładnie w jednej z części (tzn. jeśli jedna z części zawiera koralik rodzaju , to druga część nie może zawierać żadnego koralika rodzaju ). Na ile sposobów możemy to zrobić oraz jaka jest minimalna różnica długości otrzymanych części?
Pierwszy wiersz standardowego wejścia zawiera dwie liczby całkowite i () oddzielone pojedynczym odstępem, oznaczające długość naszyjnika i liczbę rodzajów koralików. Rodzaje koralików numerujemy liczbami od 1 do . Drugi wiersz wejścia zawiera ciąg liczb całkowitych () pooddzielanych pojedynczymi odstępami; liczba oznacza rodzaj koralika o numerze . Możesz założyć, że każdy rodzaj koralika wystąpi w naszyjniku co najmniej raz.
W testach wartych łącznie punktów zachodzi dodatkowy warunek .
Pierwszy i jedyny wiersz standardowego wyjścia powinien zawierać dwie liczby całkowite oddzielone pojedynczym odstępem. Pierwsza z nich ma oznaczać liczbę sposobów, na jakie można podzielić naszyjnik (możesz założyć, że dla danych wejściowych co najmniej jeden podział jest możliwy). Druga liczba ma oznaczać minimalną różnicę długości otrzymanych części.
Dla danych wejściowych:
9 5 2 5 3 2 2 4 1 1 3
poprawną odpowiedzią jest:
4 3
Wyjaśnienie do przykładu: Są cztery możliwe podziały; krótsza część może zawierać koraliki , , lub . W ostatnim przypadku uzyskujemy optymalną różnicę długości .
Testy "ocen":
Autor zadania: Jacek Tomasiewicz.
<Wyślij rozwiązanie> [0/100]